
import copy, random
from GameUtils import argmax


EMPTY = None
RED = 'red'#Computer
BLACK = 'black'#Human
infinity = 99999999
herustic_max_value = 100000

memorization_dictionary = {}
'''''''''''**************************Random Move**************************'''''''''''''''
def random_move(state, game):
    potentialMoves = game.successors(state)
    (move, state) = potentialMoves[random.randint(0, len(potentialMoves) - 1)]
    return (move, state)

'''''''''''**************************Herustic**************************'''''''''''''''
def herustic_search(state, game):
    move, state = argmax(game.successors(state),
                           lambda ((a, s)): herustic_function(s, game.width, game.height))
    return (move, state)


""" 
Offensive & Defensive Heuristic Function:Delta of COM's and HUMAN's Number of pieces in a row(horizontally+vertically+diagonally)
"""
def herustic_function(state, BOARDWIDTH, BOARDHEIGHT):
        
        board = state.board
        #COM
#        com_fours = checkForStreak(board, RED, 4,BOARDWIDTH, BOARDHEIGHT)
        com_threes = checkForStreak(board, RED, 3, BOARDWIDTH, BOARDHEIGHT)
        com_twos = checkForStreak(board, RED, 2, BOARDWIDTH, BOARDHEIGHT)
        #HUMAN
#        human_fours = checkForStreak(board, BLACK, 4,BOARDWIDTH, BOARDHEIGHT)
        human_threes = checkForStreak(board, BLACK, 3, BOARDWIDTH, BOARDHEIGHT)
        human_twos = checkForStreak(board, BLACK, 2, BOARDWIDTH, BOARDHEIGHT)
        
        com_score = com_threes * 0.7 * herustic_max_value + com_twos * 0.1 * herustic_max_value
        human_score = human_threes * 0.9 * herustic_max_value + human_twos * 0.05 * herustic_max_value
        return com_score - human_score
        
def checkForStreak(board, color, streak, BOARDWIDTH, BOARDHEIGHT):
        count = 0
        # for each piece in the board...
        for i in xrange(BOARDWIDTH):
            for j in xrange(BOARDHEIGHT):
                # ...that is of the color we're looking for...
                if board[i][j] == color:
                    # check if a vertical streak starts at (i, j)
                    count += verticalStreak(i, j, board, streak, BOARDWIDTH, BOARDHEIGHT)
                    
                    # check if a horizontal four-in-a-row starts at (i, j)
                    count += horizontalStreak(i, j, board, streak, BOARDWIDTH, BOARDHEIGHT)
                    
                    # check if a diagonal (either way) four-in-a-row starts at (i, j)
                    count += diagonalCheck(i, j, board, streak, BOARDWIDTH, BOARDHEIGHT)
        # return the sum of streaks of length 'streak'
        return count
            
def verticalStreak(row, col, board, streak, BOARDWIDTH, BOARDHEIGHT):
        consecutiveCount = 0
        for i in xrange(row, BOARDWIDTH):
            if board[i][col] == board[row][col]:
                consecutiveCount += 1
            else:
                break
    
        if consecutiveCount >= streak:
            return 1
        else:
            return 0
    
def horizontalStreak(row, col, board, streak, BOARDWIDTH, BOARDHEIGHT):
        consecutiveCount = 0
        for j in xrange(col, BOARDHEIGHT):
            if board[row][j] == board[row][col]:
                consecutiveCount += 1
            else:
                break

        if consecutiveCount >= streak:
            return 1
        else:
            return 0
    
def diagonalCheck(row, col, board, streak, BOARDWIDTH, BOARDHEIGHT):

        total = 0
        # check for diagonals with positive slope
        consecutiveCount = 0
        j = col
        for i in xrange(row, BOARDWIDTH):
            if j >= BOARDHEIGHT:
                break
            elif board[i][j] == board[row][col]:
                consecutiveCount += 1
            else:
                break
            j += 1 # increment column when row is incremented
            
        if consecutiveCount >= streak:
            total += 1

        # check for diagonals with negative slope
        consecutiveCount = 0
        j = col
        for i in xrange(row, -1, -1):
            if j >= BOARDHEIGHT:
                break
            elif board[i][j] == board[row][col]:
                consecutiveCount += 1
            else:
                break
            j += 1 # increment column when row is incremented

        if consecutiveCount >= streak:
            total += 1

        return total        
'''''''''''**************************Alpha-Beta Pruning with memorization**************************'''''''''''''''
def getDictKey(state):
    #use board configuation as key
    dict_key = repr(state.board).replace('array', ' ')
    dict_key = '' + ''.join([ c for c in dict_key if c not in ('(', ')', '[', ']', ',', "'")])
    dict_key = dict_key.replace(" ", "")
    
    return dict_key

def alphabeta_search(state, game):
    """Search game to determine best action; use alpha-beta pruning.
    This version cuts off search and uses an evaluation function."""

    def max_value(state, alpha, beta, depth,info_obj):
        if depth>info_obj.max_tree_depth:
            info_obj.max_tree_depth  = depth
        if game.cutoff_test(game,state, depth):
            return game.evaluation(state)
        v = -infinity
        for (a, s) in game.successors(state):
            #look up in the memorization_dictionary to avoid repeated state
            dictKey = getDictKey(s)
            if dictKey in memorization_dictionary:
                v = memorization_dictionary[dictKey]
                info_obj.cache_hit_count+=1
            #no history of this state,continue on alpha-beta pruning
            else:
                v = max(v, min_value(s, alpha, beta, depth + 1,info_obj))
                #add new value into the memorization_dictionary
                memorization_dictionary[dictKey] = v
                info_obj.node_count +=1
            if v >= beta:
                info_obj.max_prunning_count +=1
                return v
            alpha = max(alpha, v)
        return v

    def min_value(state, alpha, beta, depth,info_obj):
        if depth>info_obj.max_tree_depth:
            info_obj.max_tree_depth  = depth
        if game.cutoff_test(game,state, depth):
            return game.evaluation(state)
        v = infinity
        for (a, s) in game.successors(state):
            #look up in the memorization_dictionary to avoid repeated state
            dictKey = getDictKey(s)
            if dictKey in memorization_dictionary:
                v = memorization_dictionary[dictKey]
                info_obj.cache_hit_count+=1
            #no history of this state,continue on alpha-beta pruning
            else:
                v = min(v, max_value(s, alpha, beta, depth + 1,info_obj))
                #add new value into the memorization_dictionary
                memorization_dictionary[dictKey] = v
                info_obj.node_count +=1
            if v <= alpha:
                info_obj.min_prunning_count +=1
                return v
            beta = min(beta, v)
        return v

    # Body of alphabeta_search starts here:
    info_obj = GameInfo()
    #v<-Max-Value(state,-INF,+INF)
    move, state = argmax(game.successors(state),
                           lambda ((a, s)): min_value(s, -infinity, infinity, 0,info_obj))
    
    #output
    print '============================================================================================'
    print 'Maximum depth of tree:',info_obj.max_tree_depth
    print 'Total number of nodes generated:',info_obj.node_count
    print 'Total number of nodes cache hits:',info_obj.cache_hit_count
    print 'Size of nodes cache:',len(memorization_dictionary)
    print 'number of times pruning occurred within the MAX-VALUE function:',info_obj.max_prunning_count
    print 'number of times pruning occurred within the MIN-VALUE function:',info_obj.min_prunning_count
    return (move, state)



def isWinner(board, tile, BOARDWIDTH, BOARDHEIGHT):
    # check horizontal spaces
    for x in range(BOARDWIDTH - 3):
        for y in range(BOARDHEIGHT):
            if board[x][y] == tile and board[x + 1][y] == tile and board[x + 2][y] == tile and board[x + 3][y] == tile:
                return True
    # check vertical spaces
    for x in range(BOARDWIDTH):
        for y in range(BOARDHEIGHT - 3):
            if board[x][y] == tile and board[x][y + 1] == tile and board[x][y + 2] == tile and board[x][y + 3] == tile:
                return True
    # check / diagonal spaces
    for x in range(BOARDWIDTH - 3):
        for y in range(3, BOARDHEIGHT):
            if board[x][y] == tile and board[x + 1][y - 1] == tile and board[x + 2][y - 2] == tile and board[x + 3][y - 3] == tile:
                return True
    # check \ diagonal spaces
    for x in range(BOARDWIDTH - 3):
        for y in range(BOARDHEIGHT - 3):
            if board[x][y] == tile and board[x + 1][y + 1] == tile and board[x + 2][y + 2] == tile and board[x + 3][y + 3] == tile:
                return True
    return False

def isValidMove(board, column, BOARDWIDTH):
    # Returns True if there is an empty space in the given column.
    # Otherwise returns False.
    if column < 0 or column >= (BOARDWIDTH) or board[column][0] != EMPTY:
        return False
    return True


def isBoardFull(board, BOARDWIDTH, BOARDHEIGHT):
    # Returns True if there are no empty spaces anywhere on the board.
    for x in range(BOARDWIDTH):
        for y in range(BOARDHEIGHT):
            if board[x][y] == EMPTY:
                return False
    return True

def getLowestEmptySpace(board, column, BOARDHEIGHT):
    # Return the row number of the lowest empty row in the given column.
    for y in range(BOARDHEIGHT - 1, -1, -1):
        if board[column][y] == EMPTY:
            return y
    return -1

def getTileColor(enemyTile):
    if enemyTile == RED:
        return BLACK
    else:
        return RED
    
class ConnectFourGame:
    """A game is similar to a problem, but it has a utility for each
    state and a terminal test instead of a path cost and a goal
    test. To create a game, subclass this class and implement
    legal_moves, make_move, utility, and terminal_test. You may
    override display and successors or you can inherit their default
    methods. You will also need to set the .initial attribute to the
    initial state; this can be done in the constructor."""

    def __init__(self, height, width, difficulty):
        self.height = height
        self.width = width
        self.difficulty = difficulty
        
    def legal_moves(self, parentState):
        "Return a list of the allowable moves at this point."
        player_tile = getTileColor(parentState.to_move)
        moveList = []
        
        #drop a new ball
        for columnNumber in range(self.width):
            if isValidMove(parentState.board, columnNumber, self.width):
                moveList.append(('drop', columnNumber))
        #pop out a ball of one's at the bottom
        for col in range(self.width):
                if parentState.board[col][self.height - 1] == player_tile:
                    moveList.append(('pop', col))
#        print parentState.board,"----",moveList
        return moveList
    
    def make_move(self, move, parentState):
        "Return the state that results from making a move from a state."
        childTileColor = getTileColor(parentState.to_move)
        childState = ConnectFourGameState()
        newBoard = copy.deepcopy(parentState.board)
        childState.board = newBoard
        childState.to_move = childTileColor
        #pop out a ball
        if move[0] == 'pop':
            childState.board[move[1]].pop()
            childState.board[move[1]].insert(0, None)
            childState.last_move = 'pop@col:', move[1]
             
        #drop a new ball
        else:
            lowest = getLowestEmptySpace(parentState.board, move[1], self.height)
            if lowest != -1:
                childState.board[move[1]][lowest] = childTileColor
                childState.last_move = 'drop@[row:', lowest, '][col:', move[1], ']'
                
        return childState
    def cutoff_test(self,game,state,depth):
        "The default cut off happen when the depth reaches [game.difficulty] or when search reaches at a terminal state"
        return depth >=game.difficulty or self.terminal_test(state)
    
    def evaluation(self, state):
        "Return the value of this final state to player."
        if isBoardFull(state.board, self.width, self.height):#tie
            state.result = 'tie'
            return 0
        elif isWinner(state.board, state.to_move, self.width, self.height):
            if state.to_move == RED:#computer win
                return herustic_max_value * infinity
            else:            #human win
                return -herustic_max_value * infinity
        #herustic evaluation
        else:
            return herustic_function(state, self.width, self.height)
            

    def terminal_test(self, state):
        "Return True if this is a final state for the game."
        if isBoardFull(state.board, self.width, self.height) or isWinner(state.board, state.to_move, self.width, self.height):
            return True
        else:
            return False

    def to_move(self, state):
        "Return the player whose move it is in this state."
        return state.to_move

    def display(self, state):
        "Print or otherwise display the state."
        print state

    def successors(self, state):
        "Return a list of legal (move, state) pairs."
        return [(move, self.make_move(move, state))
                for move in self.legal_moves(state)]

    def __repr__(self):
        return '<%s>' % self.__class__.__name__
    
class ConnectFourGameState:
    to_move = '' #the player whose move it is in this state---Red or Black
    board = [] #board configuration after the last move
    util_value = -infinity
    last_move = ''#drop or pop out
    
class GameInfo:
    node_count = 0
    max_tree_depth = 0
    max_prunning_count = 0
    min_prunning_count = 0
    cache_hit_count = 0
